package it.storm.solution;

import java.util.Arrays;

/**
 * 1314. 矩阵区域和
 * https://leetcode-cn.com/problems/matrix-block-sum/
 */
public class Solutions_1314 {
    public static void main(String[] args) {
        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int K = 1;  // output: {{12, 21, 16}, {27, 45, 33}, {24, 39, 28}}

//        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//        int K = 2;  // output: {{45, 45, 45}, {45, 45, 45}, {45, 45, 45}}

        int[][] result = matrixBlockSum(mat, K);
        System.out.println(Arrays.deepToString(result));
    }

    /**
     * 解法二：矩阵前缀和（4ms）
     * 矩阵前缀和计算：上边和 + 左边和 + 当前元素 - 左上角和
     * 1  2  3         1   3   6
     * 4  5  6   =>    5   12  21
     * 7  8  9         12  27  45
     */
    public static int[][] matrixBlockSum(int[][] mat, int k) {
        int rows = mat.length, cols = mat[0].length;
        // preSum[1][1] = 12：即 [0][0] + [0][1] + [1][0] + [1][1]
        // [rows + 1][cols + 1] 的空间计算前缀和，多一个长度无需判断索引越界
        int[][] preSum = new int[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                // 计算前缀和
                preSum[i][j] = mat[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
            }
        }
        int[][] res = new int[rows][cols];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                // 右下角的行
                int rightDownX = i + k > rows ? rows : i + k;
                // 右下角的列
                int rightDownY = j + k > cols ? cols : j + k;
                // 左上角 - 1 的行坐标
                int leftUpX = i - k > 0 ? i - k - 1 : 0;
                // 左上角 - 1 的列坐标
                int leftUpY = j - k > 0 ? j - k - 1 : 0;
                // 右下角的值 - 左边的和 - 上边的和 + 左上角的和
                res[i - 1][j - 1] = preSum[rightDownX][rightDownY]
                                    - preSum[rightDownX][leftUpY]
                                    - preSum[leftUpX][rightDownY]
                                    + preSum[leftUpX][leftUpY];
            }
        }
        return res;
    }

    /**
     * 解法一：暴力法（134ms）
     */
    public static int[][] matrixBlockSum2(int[][] mat, int k) {
        int rows = mat.length, cols = mat[0].length;
        int[][] res = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 计算得到遍历的起始位置
                int cur = 0;
                int rowStart = Math.max(0, i - k);
                int rowEnd = Math.min(rows - 1, i + k);
                int colStart = Math.max(0, j - k);
                int colEnd = Math.min(cols - 1, j + k);
                // 循环相加
                for (int m = rowStart; m <= rowEnd; m++) {
                    for (int n = colStart; n <= colEnd; n++) {
                        cur += mat[m][n];
                    }
                }
                res[i][j] = cur;
            }
        }
        return res;
    }
}
